数据结构概念罗列

绪论

数据：信息的载体

数据元素：数据的基本单位

数据对象：数据的一个子集

数据类型：一个值的集合和定义在此集合上的一组操作的总称

  • 原子类型：值不可再分
  • 结构类型：值可再分
  • 抽象数据类型：抽象数据组织及其相关操作

数据结构：相互之间存在一种或多种特定关系的数据元素的集合

  • 逻辑结构
    • 线性结构
    • 非线性结构
  • 存储结构
    • 顺序存储
    • 链式存储
    • 索引存储
    • 散列存储
  • 数据的运算

算法：对特定问题求解的一种描述

  • 五个特性：有穷性、确定性、可行性、0个或多个输入、1个或多个输出
  • 描述算法效率的度量
    • 时间复杂度
    • 空间复杂度
      • 算法原地工作是指算法所需的辅助空间为常量，即O(1)

线性表

存储结构：

  • 顺序存储：顺序表
  • 链式存储：
    • 单链表
    • 双链表
    • 循环链表
    • 静态链表（数组实现）

栈和队列

栈和队列：操作受限的线性表

栈：

  • 顺序栈
  • 链栈
  • 共享栈

队列：

  • 循环队列
  • 链式队列
  • 双端队列

字符串

存储结构：

  • 定长顺序存储（数组）
  • 堆分配存储（动态数组）
  • 块链存储

模式匹配算法：

  • 暴力匹配法：O(mn)
  • KMP算法：通过部分匹配值避免重头匹配
  • KMP算法进一步改进：改进next数组，递归创建next数组，避免$p_j = p_{next[j]}$

树与二叉树

特点：

  • 树的根结点没有前驱结点，除根节点以为的所有结点有且只有一个直接前驱
  • 树中所有结点可以有零个或多个后继

结点的度：结点的孩子个数

分支结点：度大于0的结点

叶子结点：度为0的结点

结点的层次从根结点开始定义，根节点在第一层

结点的深度：从根结点自顶向下逐层累加

结点的高度：从叶结点开始自底向上累加

有序树：结点子树有次序，不可互换

无序树：结点子树无次序，可呼唤

路径：两个结点之间所经过的结点序列

路径长度：路径上所经过的边的个数

森林：M棵互不相交的树的集合

树最基本的性质：

  • 结点数 = 所有结点的度数+1
  • 度为m的树中，第i层至多有$m^{i-1}（i\ge1）$个结点
  • 高度为h的m叉树至多有$(m^h-1)/(m-1)$个结点
  • 具有n个结点的m叉树的最小高度为$\lceil log_m(n(m-1)+1)\rceil$

二叉树：n个结点的有限集合

  • 或者为空二叉树，n=0
  • 或者为根结点+左右子树（递归二叉树）

特殊的二叉树：

  • 满二叉树
  • 完全二叉树
  • 二叉排序树：左子树 < 根结点 < 右子树
  • 平衡二叉树：任一结点的左右子树深度之差不超过1

二叉树的性质：

  • 非空二叉树的叶子结点树等于度为2的结点数+1
  • 非空二叉树第k层至多有$2^{k-1}$个结点
  • 高度为h的二叉树至多有$2^h-1$个结点
  • 从根结点开始，从1开始编号
    • 当i > 1 时，结点 i 的双亲编号为$\lfloor i/2 \rfloor$
    • 当 2i <= n 时，左孩子存在，编号为 2i
    • 当 2i + 1 <= n 时，右孩子存在，编号为 2i + 1
  • 具有 n (n > 0) 个结点的完全二叉树的高度为$\lceil log_2(n+1) \rceil$或$\lfloor log_2n \rfloor + 1$

二叉树存储结构：

  • 顺序存储结构
  • 链式存储结构

三种常用的存储结构：

  • 双亲表示法
  • 孩子表示法
  • 孩子兄弟表示法

二叉树的遍历：根据根节点的访问顺序，递归

  • 先序遍历
  • 中序遍历
  • 后序遍历
  • 层次遍历（借助辅助队列，FIFO）

由二叉树的先序序列和中序序列可以唯一确定一棵二叉树

由二叉树的后序序列和中序序列可以唯一确定一棵二叉树

由二叉树的层序序列和中序序列可以唯一确定一棵二叉树

线索二叉树：二叉树的结点排列成一个线性序列

二叉树的线索化是将二叉链表中的空指针指向前驱或后继的线索，前驱和后继只有在遍历时才能得到，所以线索化实质是遍历一次二叉树。

树转换为二叉树规则：左孩子右兄弟

树森林二叉树
先根遍历先序遍历先序遍历
后根遍历中序遍历中序遍历

二叉树的应用

  • 二叉排序树（BST）
    • 查找：从根结点开始，二分查找
    • 插入：
      • 树空时直接插入
      • 非空时插入到查找失败时路径上的最后一个结点的左孩子或右孩子
    • 构造：依次插入
    • 删除：
      • 叶子结点直接删除
      • 若删除的结点只有一个孩子，则直接替代
      • 有两个孩子，则用直接前驱或直接后继替代
    • 查找效率
      • 平衡二叉树：$O(log_2n)$
      • 退化成链表：O(n)
  • 平衡二叉树：避免树的高度增长过快，降低二叉排序树的性能
    • 插入：
      • LL平衡旋转（右单旋转）
      • RR平衡旋转（左单旋转）
      • LR平衡旋转（先左后右双旋转）
      • RL平衡旋转（先右后左双旋转）
    • 查找：$O(log_2n)$
  • 哈夫曼树：带权路径长度（WPL）最小的二叉树，最优二叉树
    • 构造过程
      • 根据给定的 n 个权值，构造具有 n 棵扩充二叉树的森林
      • 在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，且置新树的附加根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的权值
      • 从森林中删除这两棵树，同时把新树加入到森林中
      • 重复2，3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树
    • 哈夫曼编码是一种被广泛应用且非常有效的数据压缩编码

图

图G：顶点集V和边集E组成，G=(V, E)，顶点集一定非空

有向图：E是有向边（弧）的有限集合，弧是顶点的有序对，记为<v,w>

无向图：E是无向边（边）的有限集合，边是顶点的无序对，记为(v,w)

简单图：不存在重复边，不存在顶点到自身的边

多重图：两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联

（简单）完全图：任意两个顶点之间都存在边

  • 有向：n(n-1)
  • 无向：n(n-1)/2

子图：前提是图，顶点集和边集是子集。顶点集完全一样则为生成子图。

连通：无向图中，顶点v到顶点w有路径存在

连通图：无向图中，任意两个顶点都是连通的

连通分量：无向图中的极大连通子图

强连通：有向图中，从顶点v到w和从w到v之间都有路径

强连通图：有向图中，任意一对顶点都是强连通的

强连通分量：有向图中的极大强连通子图

连通图的生成树：包含图中全部顶点的一个极小连通子图，若顶点数为n，则边数为n-1

非连通图的生成森林：连通分量的生成树

顶点的度：TD(v)

顶点的入度：ID(v)

顶点的出度：OD(v)

TD(v) = ID(v) + OD(v)

带权图（网）：有权值的图

稠密图、稀疏图：|E| < |V| log|V|时，为稀疏图，反之为稠密图

路径长度：路径上边的数目

回路（环）：若一个图有n个顶点，并且有大于 n-1 条边，则此图有环

简单路径：顶点不重复出现

简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路

距离：顶点之间的最短路径的长度，不存在路径距离为无穷

有向树：一个顶点入度为0，其余顶点入度均为1的有向图

图的存储：

  • 邻接矩阵法
  • 邻接表法
  • 十字链表法：有向图的一种链式存储结构，易求得入度和出度
  • 邻接多重表：无向图的一种链式存储结构，易得到顶点和边的各种信息，且易于判断两点之间是否存在边（邻接表的缺陷）

图的遍历：

  • 广度优先搜索（BFS），类似二叉树的层序遍历
    • 广度遍历中，可得到遍历树：广度优先生成树
      • 图的邻接矩阵存储表示唯一，故广度优先生成树也唯一
      • 图的邻接表存储表示不唯一，故广度优先生成树不唯一
  • 深度优先搜索（DFS）
    • 深度优先搜索
      • 对连通图DFS会产生一棵深度优先生成树
      • 否则产生深度优先生成森林
      • 基于邻接表存储的深度优先生成树不唯一

图的应用：

  • 最小生成（代价）树

    • 性质
      • 最小生成树（树形）不唯一
      • 最小生成树的边的权值总和唯一
      • 最小生成树的边数为定点数减一
    • 最小生成树算法（贪心策略）
      • Prim算法：$O(|V|^2)$，适合边稠密的图
      • Kruskal算法：$O(|E|log|E|)$，适合边稀疏而顶点较多的图

  • 最短路径

    • 最短路径算法依赖一种性质：两点之间的最短路径也包含了路径上的其他顶点间的最短路径
    • Dijkstra（迪杰斯特拉）算法：单源最短路径，即求图中某一顶点到其他各顶点的最短路径，不适用于边上带有负权值，$O(|V|^2)$
    • Floyd（弗洛依德）算法：求每对顶点之间的最短路径，$O(|V|^3)$，代码紧凑且不包含复杂数据结构，因此隐含的常数系数很小
      • 允许带负权值的边，但不允许有包含带负权值的边组成回路
      • 适用于带权无向图，可视为权值相同往返二重边的有向图
      • 每个顶点轮流运行一次Dijkstra算法，时间复杂度为$O(|V|^2)·|V|=O(|V|^3)$

  • 有向无环图：DAG图，描述含有公共子式的表达式的有效工具，代替二叉树可节省存储空间

  • 拓扑排序：由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

    1. 每个顶点出现且只出现一次

    2. 若顶点A在序列中排在B的前面，则不存在从B到A的路径

  • 关键路径：AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，把关键路径上面的活动称为关键活动。

    • 事件vk最早发生时间ve(k)
    • 事件vk最迟发生时间vl(k)
    • 活动ai最早开始时间e(i)
    • 活动ai最迟开始时间l(i)
    • 差额d(i) = l(i) - e(i)，差额为0的活动ai是关键活动
    • 选择题根据ve的计算过程即可知道关键路径

AOV网：若用DAG图表示一个工程，其顶点表示活动，用有向边<Vi, Vj>表示活动Vi必须先于活动Vj进行的这样一种关系，则将这种有向图称为用顶点表示活动的网络，记为AOV网。每个AOV网都有一个或多个拓扑排序序列

AOE网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销，称之为用边表示活动的网络，简称AOE网。

查找

顺序查找：

  • $ASL_{成功} = \sum_{i=1}^nP_i(n-i+1)=\frac {n+1} 2$
  • $ASL_{不成功} = n +1$
  • 有序顺序表查找判定树：$ASL_{不成功} = \frac{n}{2} + \frac{n+1}{n}$

折半查找/二分查找：

  • $ASL = log_2(n+1)-1$
  • $O(log_2n)$

分块查找

  • 块内和索引表均顺序查找：$ASL=L_i+L_S$
  • 索引表折半查找，块内顺序查找：$ASL=\lceil log_2(b+1)+\frac{s+1}{2}\rceil$

B树（多路平衡查找树）：

  • 插入：插入叶节点，溢出则分裂上移
  • 删除：
    • 非终端结点，使用前驱或后继替代
    • 终端结点：
      • 直接删除
      • 兄弟够借，父节点关键字取代删除结点，兄弟关键字结点上移
      • 兄弟不够借，父节点关键字和兄弟结点合并

B+树：操作与B树类似，但叶子结点包含信息，非叶结点仅起索引作用

散列表：建立了关键字和存储地址之间的一种之间映射关系，O(1)

  • 散列构造：
    • 直接定址法
    • 除留余数法
    • 数字分析法
    • 平方取中法
  • 处理冲突的方法
    • 开放定址法
      • 线性探测法
      • 平方探测法（二次探测法）
      • 再散列法
    • 拉链法：同义词存储在线性链表
  • 查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子
    • 装填因子，定义为一个表的装满程度，$\alpha=\frac{表中记录数n}{散列表长度m}$
    • 散列表的平均查找长度不直接依赖于n或m，装得越满，发生冲突的可能越大

排序

直接插入排序：

  • 空间复杂度$O(1)$
  • 时间复杂度$O(n^2)$

折半插入排序：折半查找插入位置，统一移动元素

希尔排序：

  • 空间复杂度$O(1)$
  • 时间复杂度$O(n^2)$

冒泡排序：

  • 空间复杂度$O(1)$
  • 时间复杂度$O(n^2)$

快速排序：

  • 空间复杂度$O(log_2n)$
  • 时间复杂度$O(nlog_2n)$
  • 所有内部排序中平均性能最优的排序算法
  • 每趟排序后会将枢轴（基准）元素放到最终位置上

简单选择排序：

  • 空间复杂度$O(1)$
  • 时间复杂度$O(n^2)$

堆排序：

  • 空间复杂度$O(1)$
  • 时间复杂度$O(nlog_2n)$

归并排序：

  • 空间复杂度$O(n)$
  • 时间复杂度$O(nlog_2n)$

基数排序

外部排序：

  • 多路平衡归并和败者树
  • 置换-选择排序（生成初始归并段）
  • 最佳归并树